{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!--NAVIGATION-->\n",
    "< [高级索引](02.07-Fancy-Indexing.ipynb) | [目录](Index.ipynb) | [格式化数据：NumPy里的结构化数组](02.09-Structured-Data-NumPy.ipynb) >\n",
    "\n",
    "<a href=\"https://colab.research.google.com/github/wangyingsm/Python-Data-Science-Handbook/blob/master/notebooks/02.08-Sorting.ipynb\"><img align=\"left\" src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open in Colab\" title=\"Open and Execute in Google Colaboratory\"></a>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sorting Arrays\n",
    "\n",
    "# 数组排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Up to this point we have been concerned mainly with tools to access and operate on array data with NumPy.\n",
    "This section covers algorithms related to sorting values in NumPy arrays.\n",
    "These algorithms are a favorite topic in introductory computer science courses: if you've ever taken one, you probably have had dreams (or, depending on your temperament, nightmares) about *insertion sorts*, *selection sorts*, *merge sorts*, *quick sorts*, *bubble sorts*, and many, many more.\n",
    "All are means of accomplishing a similar task: sorting the values in a list or array.\n",
    "\n",
    "本节之前，我们主要关注NumPy中那些获取和操作数组数据的工具。本小节我们会介绍对NumPy数组进行排序的算法。这些算法在基础计算机科学领域是很热门的课题：如果你学习过相关的课程的话，你可能梦（或者根据你的经理，可能是噩梦）到过有关*插入排序*、*选择排序*、*归并排序*、*快速排序*、*冒泡排序*和其他很多很多名词。这些都是为了完成一件工作的：对数组进行排序。\n",
    "\n",
    "> For example, a simple *selection sort* repeatedly finds the minimum value from a list, and makes swaps until the list is sorted. We can code this in just a few lines of Python:\n",
    "\n",
    "例如，一个简单的*选择排序*会重复寻找列表中最小的值，然后和当前值进行交换，直到列表排序完成。我们可以在Python中用简单的几行代码完成这个算法："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def selection_sort(x):\n",
    "    for i in range(len(x)):\n",
    "        swap = i + np.argmin(x[i:]) # 寻找子数组中的最小值的索引序号\n",
    "        (x[i], x[swap]) = (x[swap], x[i]) # 交换当前值和最小值\n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 2, 3, 4, 5])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = np.array([2, 1, 4, 3, 5])\n",
    "selection_sort(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> As any first-year computer science major will tell you, the selection sort is useful for its simplicity, but is much too slow to be useful for larger arrays.\n",
    "For a list of $N$ values, it requires $N$ loops, each of which does on order $\\sim N$ comparisons to find the swap value.\n",
    "In terms of the \"big-O\" notation often used to characterize these algorithms (see [Big-O Notation](#Aside:-Big-O-Notation)), selection sort averages $\\mathcal{O}[N^2]$: if you double the number of items in the list, the execution time will go up by about a factor of four.\n",
    "\n",
    "任何一个5年的计算机科学专业都会教你，选择排序很简单，但是对于大的数组来说运行效率就不够了。对于数组具有$N$个值，它需要$N$次循环，每次循环中需要$\\sim N$次比较和寻找来交换元素。*大O*表示法经常用来对算法性能进行定量分析（参见[大O复杂度](#Aside:-Big-O-Notation)），选择排序平均需要$\\mathcal{O}[N^2]$：如果列表中的元素个数加倍，执行时间增长大约是原来的4倍。\n",
    "\n",
    "> Even selection sort, though, is much better than my all-time favorite sorting algorithms, the *bogosort*:\n",
    "\n",
    "甚至选择排序也远比下面这个*bogo排序*算法有效地多，这是作者最喜爱的排序算法："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bogosort(x):\n",
    "    while np.any(x[:-1] > x[1:]):\n",
    "        np.random.shuffle(x)\n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 2, 3, 4, 5])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = np.array([2, 1, 4, 3, 5])\n",
    "bogosort(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> This silly sorting method relies on pure chance: it repeatedly applies a random shuffling of the array until the result happens to be sorted.\n",
    "With an average scaling of $\\mathcal{O}[N \\times N!]$, (that's *N* times *N* factorial) this should–quite obviously–never be used for any real computation.\n",
    "\n",
    "这个有趣而粗苯的算法完全依赖于概率：它重复的对数组进行随机的乱序直到结果刚好是正确排序为止。这个算法平均需要$\\mathcal{O}[N \\times N!]$，即*N*乘以*N*的阶乘，明显的，在真实情况下，它不应该被用于排序计算。\n",
    "\n",
    "> Fortunately, Python contains built-in sorting algorithms that are *much* more efficient than either of the simplistic algorithms just shown. We'll start by looking at the Python built-ins, and then take a look at the routines included in NumPy and optimized for NumPy arrays.\n",
    "\n",
    "幸运的是，Python內建有了排序算法，比我们刚才提到那些简单的算法都要高效。我们从Python內建的排序开始介绍，然后再去讨论NumPy中为了数组优化的排序函数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fast Sorting in NumPy: ``np.sort`` and ``np.argsort``\n",
    "\n",
    "## NumPy中快速排序：`np.sort` 和 `np.argsort`\n",
    "\n",
    "> Although Python has built-in ``sort`` and ``sorted`` functions to work with lists, we won't discuss them here because NumPy's ``np.sort`` function turns out to be much more efficient and useful for our purposes.\n",
    "By default ``np.sort`` uses an $\\mathcal{O}[N\\log N]$, *quicksort* algorithm, though *mergesort* and *heapsort* are also available. For most applications, the default quicksort is more than sufficient.\n",
    "\n",
    "虽然Python有內建的`sort`和`sorted`函数可以用来对列表进行排序，我们在这里不讨论它们。因为NumPy的`np.sort`函数有着更加优秀的性能，而且也更满足我们要求。默认情况下`np.sort`使用的是$\\mathcal{O}[N\\log N]$*快速排序*排序算法，*归并排序*和*堆排序*也是可选的。对于大多数的应用场景来说，默认的快速排序都能满足要求。\n",
    "\n",
    "> To return a sorted version of the array without modifying the input, you can use ``np.sort``:\n",
    "\n",
    "对数组进行排序，返回排序后的结果，不改变原始数组的数据，你应该使用`np.sort`："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 2, 3, 4, 5])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = np.array([2, 1, 4, 3, 5])\n",
    "np.sort(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> If you prefer to sort the array in-place, you can instead use the ``sort`` method of arrays:\n",
    "\n",
    "如果你期望直接改变数组的数据进行排序，你可以对数组对象使用它的`sort`方法："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1 2 3 4 5]\n"
     ]
    }
   ],
   "source": [
    "x.sort()\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> A related function is ``argsort``, which instead returns the *indices* of the sorted elements:\n",
    "\n",
    "相关的函数是`argsort`，它将返回排好序后元素原始的序号序列："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1 0 3 2 4]\n"
     ]
    }
   ],
   "source": [
    "x = np.array([2, 1, 4, 3, 5])\n",
    "i = np.argsort(x)\n",
    "print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> The first element of this result gives the index of the smallest element, the second value gives the index of the second smallest, and so on.\n",
    "These indices can then be used (via fancy indexing) to construct the sorted array if desired:\n",
    "\n",
    "结果的第一个元素是数组中最小元素的序号，第二个元素是数组中第二小元素的序号，以此类推。这些序号可以通过高级索引的方式使用，从而获得一个排好序的数组：\n",
    "\n",
    "译者注：更好的问题应该是，假如我们希望获得数组中第二、三小的元素，我们可以这样做：\n",
    "\n",
    "```python\n",
    "x[i[1:3]]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 2, 3, 4, 5])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x[i]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sorting along rows or columns\n",
    "\n",
    "### 按照行或列进行排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> A useful feature of NumPy's sorting algorithms is the ability to sort along specific rows or columns of a multidimensional array using the ``axis`` argument. For example:\n",
    "\n",
    "NumPy的排序算法可以沿着多维数组的某些轴`axis`进行，如行或者列。例如："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[6 3 7 4 6 9]\n",
      " [2 6 7 4 3 7]\n",
      " [7 2 5 4 1 7]\n",
      " [5 1 4 0 9 5]]\n"
     ]
    }
   ],
   "source": [
    "rand = np.random.RandomState(42)\n",
    "X = rand.randint(0, 10, (4, 6))\n",
    "print(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[2, 1, 4, 0, 1, 5],\n",
       "       [5, 2, 5, 4, 3, 7],\n",
       "       [6, 3, 7, 4, 6, 7],\n",
       "       [7, 6, 7, 4, 9, 9]])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 沿着每列对数据进行排序\n",
    "np.sort(X, axis=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[3, 4, 6, 6, 7, 9],\n",
       "       [2, 3, 4, 6, 7, 7],\n",
       "       [1, 2, 4, 5, 7, 7],\n",
       "       [0, 1, 4, 5, 5, 9]])"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 沿着每行对数据进行排序\n",
    "np.sort(X, axis=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Keep in mind that this treats each row or column as an independent array, and any relationships between the row or column values will be lost!\n",
    "\n",
    "必须注意的是，这样的排序会独立的对每一行或者每一列进行排序。因此结果中原来行或列之间的联系都会丢失。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Partial Sorts: Partitioning\n",
    "\n",
    "## 部分排序：分区\n",
    "\n",
    "> Sometimes we're not interested in sorting the entire array, but simply want to find the *k* smallest values in the array. NumPy provides this in the ``np.partition`` function. ``np.partition`` takes an array and a number *K*; the result is a new array with the smallest *K* values to the left of the partition, and the remaining values to the right, in arbitrary order:\n",
    "\n",
    "有时候我们并不是需要对整个数组排序，而仅仅需要找到数组中的*K*个最小值。NumPy提供了`np.partition`函数来完成这个任务；结果会分为两部分，最小的*K*个值位于结果数组的左边，而其余的值位于数组的右边，顺序随机："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([2, 1, 3, 4, 6, 5, 7])"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = np.array([7, 2, 3, 1, 6, 5, 4])\n",
    "np.partition(x, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Note that the first three values in the resulting array are the three smallest in the array, and the remaining array positions contain the remaining values.\n",
    "Within the two partitions, the elements have arbitrary order.\n",
    "\n",
    "你可以看到结果中最小的三个值在左边，其余4个值位于数组的右边，每个分区内部，元素的顺序是任意的。\n",
    "\n",
    "> Similarly to sorting, we can partition along an arbitrary axis of a multidimensional array:\n",
    "\n",
    "和排序一样，我们可以按照任意维度对一个多维数组进行分区："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[3, 4, 6, 7, 6, 9],\n",
       "       [2, 3, 4, 7, 6, 7],\n",
       "       [1, 2, 4, 5, 7, 7],\n",
       "       [0, 1, 4, 5, 9, 5]])"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.partition(X, 2, axis=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> The result is an array where the first two slots in each row contain the smallest values from that row, with the remaining values filling the remaining slots.\n",
    "\n",
    "结果中每行的前两个元素就是该行最小的两个值，该行其余的值会出现在后面。\n",
    "\n",
    "> Finally, just as there is a ``np.argsort`` that computes indices of the sort, there is a ``np.argpartition`` that computes indices of the partition.\n",
    "We'll see this in action in the following section.\n",
    "\n",
    "最后，就像`np.argsort`函数可以返回排好序的元素序号一样，`np.argpartition`可以计算分区后元素的序号。后面的例子中我们会看到它的使用。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example: k-Nearest Neighbors\n",
    "\n",
    "## 例子：k近邻\n",
    "\n",
    "> Let's quickly see how we might use this ``argsort`` function along multiple axes to find the nearest neighbors of each point in a set.\n",
    "We'll start by creating a random set of 10 points on a two-dimensional plane.\n",
    "Using the standard convention, we'll arrange these in a $10\\times 2$ array:\n",
    "\n",
    "下面我们使用`argsort`沿着多个维度来寻找每个点的最近邻。首先在一个二维平面上创建10个随机点数据。按照管理，这将是一个$10\\times 2$的数组："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = rand.rand(10, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> To get an idea of how these points look, let's quickly scatter plot them:\n",
    "\n",
    "我们先来观察一下这些点的分布情况，散点图很适合这种情形："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXgAAAD7CAYAAABgzo9kAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjAsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+17YcXAAAaSElEQVR4nO3dfUxUZ74H8O/M0fFlZVOZDjCs9Jpqw85V6CZWdt2UvggyVAeH9qrcizZ1STF3abqJzW3WblZeatMtf+xNqiu76SZauzS3Xf4oxlkCxNvesvZSsU0j6FSbUqwYBgYHTVWkM5x57h+uXCmWOcCZt+d8P4l/UB7O+f0C/c4zz5zzHJMQQoCIiKRjjncBREQUHQx4IiJJMeCJiCTFgCcikhQDnohIUgx4IiJJMeCJiCQ1L94F3OnKlRsIh+d2Wb7VugSBwHWdKkp8RusXMF7PRusXMF7Ps+3XbDZh6dIffO/3Eyrgw2Ex54C/fRwjMVq/gPF6Nlq/gPF6jka/XKIhIpIUA56ISFIRA76+vh7r169HdnY2vvjii7uOUVUVdXV1KCwsxIYNG9DU1KR7oURENDMRA76goABvv/02fvSjH33vmGPHjuHixYtob2/Hu+++iwMHDuDSpUu6FkpERDMTMeAfeugh2O32ace0tLRg69atMJvNSE1NRWFhIVpbW3UrkoiIZk6XNXifz4fMzMyJr+12OwYHB/U4NBERzVJCXSZptS7R5Tg2W4qmcb7LN/Deh1/ifz69hLFvx7FwwTw8tmYZnnx0Jez3fv+1pYlGa78yMVrPRusXMF7P0ehXl4C32+0YGBhAbm4ugKkzeq0CgetzvhbUZkvB8PC1iOO6ewNoaO6Bqgqo/zjnzW/H0f7x1/jvUxdRVZqD3BXWOdUSC1r7lYnRejZav4Dxep5tv2azadqJsS5LNMXFxWhqakI4HMbIyAiOHz8Op9Opx6Gjwn9lFA3NPQiGwhPhfpsaFgiGwmho7oH/ymicKiQimruIAf/KK6/gkUceweDgIH7xi19g06ZNAIDKykr09PQAANxuN5YtW4aioiJs27YNzz33HLKysqJb+Ry0dfVDVad/p6CqAu2n+mNUERGR/kyJ9EzWWC3RVP3nhxgLqhGPtcii4OALj86pnmgz2ltZwHg9G61fwHg9J/QSTbLREu4zGUdElIgMGfALLYqu44iIEpEhA37dqgwoZtO0YxSzCetWZ8SoIiIi/Rky4J15WVCUCAGvmFC0NnE/KCYiisSQAZ+2dDGqSnNgmW+eMpNXzCZY5ptRVZqDtKWL41QhEdHcJdSdrLGUu8KKlyvy0H6qH51nBjEWVLHQomDd6gwUrc1iuBNR0jNswAO3ZvI7irKxoyg73qUQEenOkEs0RERGwIAnIpIUA56ISFIMeCIiSTHgiYgkxYAnIpIUA56ISFIMeCIiSTHgiYgkxYAnIpIUA56ISFIMeCIiSTHgiYgkxYAnIpIUA56ISFIMeCIiSTHgiYgkxYAnIpIUA56ISFIMeCIiSTHgiYgkxYAnIpIUA56ISFIMeCIiSc3TMqivrw979uzB1atXcc8996C+vh7Lly+fNCYQCOCll16Cz+dDKBTCz372M/z2t7/FvHmaTkFERDrTNIOvqalBeXk52traUF5ejurq6ilj/vSnP2HFihU4duwYjh07hrNnz6K9vV33gomISJuIAR8IBOD1euFyuQAALpcLXq8XIyMjk8aZTCbcuHED4XAYwWAQoVAI6enp0amaiIgiirh+4vP5kJ6eDkVRAACKoiAtLQ0+nw+pqakT46qqqvD888/j4Ycfxs2bN7F9+3asWbNmRsVYrUtmWP7d2WwpuhwnWRitX8B4PRutX8B4PUejX90WyFtbW5GdnY0jR47gxo0bqKysRGtrK4qLizUfIxC4jnBYzKkOmy0Fw8PX5nSMZGK0fgHj9Wy0fgHj9Tzbfs1m07QT44hLNHa7HUNDQ1BVFQCgqir8fj/sdvukcY2Njdi8eTPMZjNSUlKwfv16nDx5csYFExGRPiIGvNVqhcPhgMfjAQB4PB44HI5JyzMAsGzZMnR0dAAAgsEgOjs78cADD0ShZCIi0kLTVTS1tbVobGyE0+lEY2Mj6urqAACVlZXo6ekBAPzmN7/Bp59+ipKSEpSWlmL58uXYtm1b9ConIqJpmYQQc1v01hHX4GfOaP0CxuvZaP0Cxus5bmvwRESUnBjwRESSYsATEUmKAU9EJCkGPBGRpBjwRESSYsATEUmKAU9EJCkGPBGRpBjwRESSYsATEUmKAU9EJCkGPBGRpHR7ohMRUSLwXxlFW1c/Os8OYiyoYqFFwbpVGXDmZSFt6eJ4lxdTDHgikkZ3bwANzT1QVQH1H1uPjwVVdJwewEdnfKgqzUHuCmucq4wdLtEQkRT8V0bR0NyDYCg8Ee63qWGBYCiMhuYe+K+MxqnC2GPAE5EU2rr6oarTPzBIVQXaT/XHqKL4Y8ATkRQ6zw5Ombl/lxoW6DwzGKOK4o8BT0RSGAuquo6TAQOeiKSw0KLoOk4GDHgiksK6VRlQzKZpxyhmE9atzohRRfHHgCciKTjzsqAoEQJeMaFobVaMKoo/BjwRSSFt6WJUlebAMt88ZSavmE2wzDejqjTHUDc78UYnIpJG7gorXq7IQ/upfnSeueNO1tUZKFrLO1mJiJJa2tLF2FGUjR1F2fEuJe64RENEJCkGPBGRpBjwRESSYsATEUmKAU9EJClNAd/X14eysjI4nU6UlZXhwoULdx3X0tKCkpISuFwulJSU4PLly3rWSkREM6DpMsmamhqUl5fD7Xbj6NGjqK6uxltvvTVpTE9PD/7whz/gyJEjsNlsuHbtGiwWS1SKJiKiyCLO4AOBALxeL1wuFwDA5XLB6/ViZGRk0rg333wTFRUVsNlsAICUlBQsWLAgCiUTEZEWEQPe5/MhPT0dinJrBzZFUZCWlgafzzdpXG9vL/r7+7F9+3Y8+eSTaGhogBDT781MRETRo9udrKqq4vz58zh8+DCCwSCeffZZZGZmorS0VPMxrNYlutRis6XocpxkYbR+AeP1bLR+AeP1HI1+Iwa83W7H0NAQVFWFoihQVRV+vx92u33SuMzMTBQXF8NiscBisaCgoADd3d0zCvhA4DrCEZ7IEonNloLh4WtzOkYyMVq/gPF6Nlq/gPF6nm2/ZrNp2olxxIC3Wq1wOBzweDxwu93weDxwOBxITU2dNM7lcuHDDz+E2+3G+Pg4Pv74YzidzhkXTESU6PxXRtHW1Y/Os3dsaLYqA868xNrQTNNlkrW1tWhsbITT6URjYyPq6uoAAJWVlejp6QEAbNq0CVarFRs3bkRpaSlWrlyJLVu2RK9yIqI46O4NoPpQFzpOD0w8/m8sqKLj9ACqD3WhuzcQ5wr/n0kk0CehXKKZOaP1CxivZ6P1CyRuz/4ro6g+1IVgKPy9YyzzzXi5Im9GM/loLdHwTlYiIo3auvqhqtNPQlVVoP1Uf4wqmh4DnohIo86zg1AjrDKoYYHOM4Mxqmh6DHgiIo1ur7nrNS7aGPBERBottCi6jos2BjwRkUbrVmVMeaD3dylmE9atzohRRdNjwBMRaeTMy4KiRAh4xYSitVkxqmh6DHgiIo3Sli5GVWkOLPPNU2byitkEy3wzqkpzEuZmJ932oiEiMoLcFVa8XJGH9lP96Dxzx52sqzNQtDax7mRlwBMRzVDa0sXYUZSNHUXZ8S5lWlyiISKSFAOeiEhSDHgiIkkx4ImIJMWAJyKSFAOeiEhSDHgiIknxOngioiiL1yP+GPBERFHU3RtAQ3MPVFVM7CV/+xF/H53xoao0BwW2lKicm0s0RERR4r8yiobmHgRD4SkPClHDAsFQGA3NPfBdvhGV8zPgiYiiROsj/o52fBmV8zPgiYiiROsj/j749FJUzs+AJyKKEq2P7rv57XhUzs+AJyKKEq2P7lu0IDrXuzDgiYiiROsj/h5fsywq52fAExFFidZH/LkfWRmV8zPgiYiiROsj/uz3/iAq5+eNTkREURTPR/wx4ImIoixej/jjEg0RkaQ4gyeapXhtIEWklaYZfF9fH8rKyuB0OlFWVoYLFy5879ivvvoKDz74IOrr6/WqkSjhdPcGUH2oCx2nByZuZrm9gVT1oS509wbiXCGRxoCvqalBeXk52traUF5ejurq6ruOU1UVNTU1KCws1LVIokSidQMp/5XROFVIdEvEJZpAIACv14vDhw8DAFwuF/bt24eRkRGkpqZOGvvGG2/gsccew+joKEZH+cdNctK6gVT7qX7dP1TjshDNRMQZvM/nQ3p6OhTl1i23iqIgLS0NPp9v0rhz587hxIkT2LlzZ1QKJUoUWjeQ6jwzqOt5uSxEM6XLh6yhUAh79+7F7373u4kXgtmwWpfoUQ5sUdo8P1EZrV8gvj1/q3EDqbGQqlud4yYz/th8BsFQeMr31PCtB0n8sfkMDvzH41G7aSbWjPZ3HY1+Iwa83W7H0NAQVFWFoihQVRV+vx92u31izPDwMC5evIhdu3YBAL755hsIIXD9+nXs27dPczGBwHWEI8yMIrHZUjA8fG1Ox0gmRusXiH/PCyyKpl0CF85XdKnTZkvBf7V+jnF1arjfaVwN4522z2N+rXU0xPt3HGuz7ddsNk07MY4Y8FarFQ6HAx6PB263Gx6PBw6HY9L6e2ZmJk6ePDnx9YEDBzA6Oopf//rXMy6YKNGtW5WBjtMD0y7TKGYT1q3O0O2cM1kWkiHgSR+arqKpra1FY2MjnE4nGhsbUVdXBwCorKxET09PVAskSjRaN5AqWpul2zm17iuudRwZg6Y1+BUrVqCpqWnKf//zn/981/HPP//83KoiSmC3N5D67oOUgVszd0Uxoao0R9erWhZqXRbSuP84GQO3KiCahdsbSD36k0wssigwAVhkUfDoTzLxckUecldYdT2f1n3F9VwWouTHrQqIZimWG0g587Lw0Rnf9Ov+Oi8LUfLjDJ4oCWjdV5w3O9GdOIMnShLx3FeckhMDniiJxGtfcUpOXKIhIpIUA56ISFIMeCIiSTHgiYgkxYAnIpIUA56ISFIMeCIiSTHgiYgkxYAnIpIUA56ISFIMeCIiSTHgiYgkxYAnIpIUA56ISFIMeCIiSTHgiYgkxYAnIpIUA56ISFIMeCIiSTHgiYgkxYAnIpIUA56ISFIMeCIiSTHgiYgkxYAnIpIUA56ISFLztAzq6+vDnj17cPXqVdxzzz2or6/H8uXLJ405ePAgWlpaoCgK5s2bh927dyM/Pz8aNRMRkQaaAr6mpgbl5eVwu904evQoqqur8dZbb00ak5ubi4qKCixatAjnzp3Djh07cOLECSxcuDAqhRMR0fQiLtEEAgF4vV64XC4AgMvlgtfrxcjIyKRx+fn5WLRoEQAgOzsbQghcvXo1CiUTEZEWEWfwPp8P6enpUBQFAKAoCtLS0uDz+ZCamnrXn2lubsZ9992HjIyMGRVjtS6Z0fjvY7Ol6HKcZGG0fgHj9Wy0fgHj9RyNfjUt0cxEV1cXXn/9dRw6dGjGPxsIXEc4LOZ0fpstBcPD1+Z0jGRitH4B4/VstH4B4/U8237NZtO0E+OISzR2ux1DQ0NQVRUAoKoq/H4/7Hb7lLGfffYZXnzxRRw8eBD333//jIslIiL9RAx4q9UKh8MBj8cDAPB4PHA4HFOWZ7q7u7F7927s378fq1atik61RESkmabr4Gtra9HY2Ain04nGxkbU1dUBACorK9HT0wMAqKurw9jYGKqrq+F2u+F2u3H+/PnoVU5ERNMyCSHmtuitI67Bz5zR+gWM17PR+gWM13Pc1uCJiCg5MeCJiCTFgCcikhQDnohIUgx4IiJJMeCJiCTFgCcikhQDnohIUgx4IiJJMeCJiCTFgCcikpTu+8FT4vBfGUVbVz86zw5iLKhioUXBulUZcOZlIW3p4niXR0RRxoCXVHdvAA3NPVBVAfUfG7iNBVV0nB7AR2d8qCrNQe4Ka5yrJKJo4hKNhPxXRtHQ3INgKDwR7repYYFgKIyG5h74r4zGqUIiigUGvITauvqhqtNvu6yqAu2n+mNUERHFAwNeQp1nB6fM3L9LDQt0nhmMUUVEFA8MeAmNBVVdxxFRcmLAS2ihRdF1HBElJwa8hNatyoBiNk07RjGbsG51RowqIqJ4YMBLyJmXBUWJEPCKCUVrs2JUERHFAwNeQmlLF6OqNAeW+eYpM3nFbIJlvhlVpTm82YlIcrzRSVK5K6x4uSIP7af60XnmjjtZV2egaC3vZCUyAga8xNKWLsaOomzsKMqOdylEFAdcoiEikpRUM3j/lVE0dXyFDz7p5+ZaRGR40gQ8N9eSB3fBJNKHFAF/5+Za36WGbwV+Q3MPXq7IY0AkOC0v1AW2lBkdky8YZFRSrMFzcy05aN0F03f5huZjdvcGUH2oCx2nBya2Zrj9glF9qAvdvQFdeyBKJFIEPDfXkoPWF+qjHV9qOh63TSajkyLgubmWHLS+UH/w6SVNx+M7OzI6TQHf19eHsrIyOJ1OlJWV4cKFC1PGqKqKuro6FBYWYsOGDWhqatK71u/FzbXkoPUF+Oa345rG8Z0dGZ2mgK+pqUF5eTna2tpQXl6O6urqKWOOHTuGixcvor29He+++y4OHDiAS5e0zbTmiptryUHrC/CiBdquDeA7OzK6iAEfCATg9XrhcrkAAC6XC16vFyMjI5PGtbS0YOvWrTCbzUhNTUVhYSFaW1ujU/V3cHMtOWh9oX58zTJNx+M7OzK6iAHv8/mQnp4ORbn1P4GiKEhLS4PP55syLjMzc+Jru92OwcHYvPXl5lpy0PpC7X5kpabj8Z0dGV1CXQdvtS6Z9c8W2FLwzyttONrxJT749BJufjuORQvm4fE1y+B+ZCXs9/5Ax0oTi22G14UnKpstBS89k4fXjpzCuDr5yhfFbMI8xYw9z6zV/Lv8t2IH/vfMINTw9y/BzFPM+FenA7YE//uQ5Xc8E0brORr9Rgx4u92OoaEhqKoKRVGgqir8fj/sdvuUcQMDA8jNzQUwdUavRSBwHeEIH4pNZx6Af3/qQfxL/v2TvyHCGB6+NuvjJjKbLUWq3v7p3sWoq1gbcRdMLT3PA/DL0tVTbpwCbr1gKIoJvyxdjXkJ/vch2+9YC6P1PNt+zWbTtBPjiAFvtVrhcDjg8Xjgdrvh8XjgcDiQmpo6aVxxcTGamppQVFSEq1ev4vjx43j77bdnXDCRnrtgcttkMjJNSzS1tbXYs2cPGhoa8MMf/hD19fUAgMrKSvzqV79CTk4O3G43Tp8+jaKiIgDAc889h6wsfqhJ8cdtk8moTEKI2a+J6GyuSzQA39oZgdF6Nlq/gPF6jtYSjRR3shIR0VQMeCIiSTHgiYgkxYAnIpIUA56ISFIJdSerOcJt5bE+TrIwWr+A8Xo2Wr+A8XqeTb+RfiahLpMkIiL9cImGiEhSDHgiIkkx4ImIJMWAJyKSFAOeiEhSDHgiIkkx4ImIJMWAJyKSFAOeiEhSSRnwfX19KCsrg9PpRFlZGS5cuDBljKqqqKurQ2FhITZs2ICmpqbYF6oTLf0ePHgQmzZtwubNm/HUU0/h73//e+wL1ZGWnm/76quv8OCDD048aSwZae23paUFJSUlcLlcKCkpweXLl2NbqI609BwIBLBr1y6UlJSguLgYtbW1GB8fj32xOqivr8f69euRnZ2NL7744q5jdM8tkYSefvpp0dzcLIQQorm5WTz99NNTxrz33nuioqJCqKoqAoGAyM/PF/39/bEuVRda+u3o6BCjo6NCCCE+//xzsWbNGnHz5s2Y1qknLT0LIcT4+LjYsWOHeOGFF8Rrr70WyxJ1paXf7u5u8cQTTwi/3y+EEOKbb74RY2NjMa1TT1p6fuWVVyZ+r8FgUGzZskX87W9/i2mdejl16pQYGBgQjz/+uDh//vxdx+idW0k3gw8EAvB6vXC5XAAAl8sFr9eLkZGRSeNaWlqwdetWmM1mpKamorCwEK2trfEoeU609pufn49FixYBALKzsyGEwNWrV2Nerx609gwAb7zxBh577DEsX748xlXqR2u/b775JioqKmCz2QAAKSkpWLBgQczr1YPWnk0mE27cuIFwOIxgMIhQKIT09PR4lDxnDz30EOx2+7Rj9M6tpAt4n8+H9PR0KIoCAFAUBWlpafD5fFPGZWZmTnxtt9sxODgY01r1oLXfOzU3N+O+++5DRkZGrMrUldaez507hxMnTmDnzp1xqFI/Wvvt7e1Ff38/tm/fjieffBINDQ0QSbpXoNaeq6qq0NfXh4cffnji35o1a+JRckzonVtJF/A0va6uLrz++uv4/e9/H+9SoioUCmHv3r2oq6ubCAnZqaqK8+fP4/Dhw/jLX/6Cjo4OHD16NN5lRVVrayuys7Nx4sQJdHR04JNPPknKd+LxknQBb7fbMTQ0BFVVAdz6o/f7/VPe+tjtdgwMDEx87fP5knJGq7VfAPjss8/w4osv4uDBg7j//vtjXaputPQ8PDyMixcvYteuXVi/fj2OHDmCv/71r9i7d2+8yp41rb/jzMxMFBcXw2KxYMmSJSgoKEB3d3c8Sp4zrT03NjZi8+bNMJvNSElJwfr163Hy5Ml4lBwTeudW0gW81WqFw+GAx+MBAHg8HjgcDqSmpk4aV1xcjKamJoTDYYyMjOD48eNwOp3xKHlOtPbb3d2N3bt3Y//+/Vi1alU8StWNlp4zMzNx8uRJvP/++3j//ffxzDPPYNu2bdi3b1+8yp41rb9jl8uFEydOQAiBUCiEjz/+GD/+8Y/jUfKcae152bJl6OjoAAAEg0F0dnbigQceiHm9saJ7bs3649k4+vLLL8WWLVtEUVGR2LJli+jt7RVCCPHss8+K7u5uIcStqyuqq6tFQUGBKCgoEO+88048S54TLf0+9dRT4qc//anYvHnzxL9z587Fs+w50dLznfbv35/UV9Fo6VdVVfHqq6+K4uJisXHjRvHqq68KVVXjWfacaOn566+/Fjt37hQul0s88cQTora2VoRCoXiWPWv79u0T+fn5wuFwiJ///Odi48aNQojo5haf6EREJKmkW6IhIiJtGPBERJJiwBMRSYoBT0QkKQY8EZGkGPBERJJiwBMRSYoBT0Qkqf8D5M0KNu9KatUAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn; seaborn.set() # 图表风格，seaborn\n",
    "plt.scatter(X[:, 0], X[:, 1], s=100);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Now we'll compute the distance between each pair of points.\n",
    "Recall that the squared-distance between two points is the sum of the squared differences in each dimension;\n",
    "using the efficient broadcasting ([Computation on Arrays: Broadcasting](02.05-Computation-on-arrays-broadcasting.ipynb)) and aggregation ([Aggregations: Min, Max, and Everything In Between](02.04-Computation-on-arrays-aggregates.ipynb))  routines provided by NumPy we can compute the matrix of square distances in a single line of code:\n",
    "\n",
    "现在让我们来计算每两个点之间的距离。距离平方的定义是两点坐标差的平方和。应用广播（[在数组上计算：广播](02.05-Computation-on-arrays-broadcasting.ipynb)）和聚合([聚合：Min, Max, 以及其他](02.04-Computation-on-arrays-aggregates.ipynb))函数，我们可以使用一行代码就能计算出所有点之间的距离平方："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "dist_sq = np.sum((X[:, np.newaxis, :] - X[np.newaxis, :, :]) ** 2, axis=-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> This operation has a lot packed into it, and it might be a bit confusing if you're unfamiliar with NumPy's broadcasting rules. When you come across code like this, it can be useful to break it down into its component steps:\n",
    "\n",
    "上面的这行代码包含很多的内容值得探讨，如果对于不是特别熟悉广播机制的读者来说，看起来可能会让人难以理解。当你读到这样的代码的时候，将它们打散成一步步的操作会有帮助："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10, 10, 2)"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 计算每两个点之间的坐标距离\n",
    "differences = X[:, np.newaxis, :] - X[np.newaxis, :, :]\n",
    "differences.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10, 10, 2)"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 计算距离的平方\n",
    "sq_differences = differences ** 2\n",
    "sq_differences.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10, 10)"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 按照最后一个维度求和\n",
    "dist_sq = sq_differences.sum(-1)\n",
    "dist_sq.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Just to double-check what we are doing, we should see that the diagonal of this matrix (i.e., the set of distances between each point and itself) is all zero:\n",
    "\n",
    "你可以检查这个矩阵的对角线元素，对角线元素的值是点与其自身的距离平方，应该全部为0："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0., 0., 0., 0., 0., 0., 0., 0., 0., 0.])"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dist_sq.diagonal()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> It checks out!\n",
    "With the pairwise square-distances converted, we can now use ``np.argsort`` to sort along each row. The leftmost columns will then give the indices of the nearest neighbors:\n",
    "\n",
    "确认正确。现在我们已经有了一个距离平方的矩阵，然后就可以使用`np.argsort`函数来按照每行来排序。最左边的列就会给出每个点的最近邻："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 3 9 7 1 4 2 5 6 8]\n",
      " [1 4 7 9 3 6 8 5 0 2]\n",
      " [2 1 4 6 3 0 8 9 7 5]\n",
      " [3 9 7 0 1 4 5 8 6 2]\n",
      " [4 1 8 5 6 7 9 3 0 2]\n",
      " [5 8 6 4 1 7 9 3 2 0]\n",
      " [6 8 5 4 1 7 9 3 2 0]\n",
      " [7 9 3 1 4 0 5 8 6 2]\n",
      " [8 5 6 4 1 7 9 3 2 0]\n",
      " [9 7 3 0 1 4 5 8 6 2]]\n"
     ]
    }
   ],
   "source": [
    "nearest = np.argsort(dist_sq, axis=1)\n",
    "print(nearest)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Notice that the first column gives the numbers 0 through 9 in order: this is due to the fact that each point's closest neighbor is itself, as we would expect.\n",
    "\n",
    "结果中的第一列是0到9的数字：这是因为距离每个点最近的是自己，正如我们预料的一样。\n",
    "\n",
    "> By using a full sort here, we've actually done more work than we need to in this case. If we're simply interested in the nearest $k$ neighbors, all we need is to partition each row so that the smallest $k + 1$ squared distances come first, with larger distances filling the remaining positions of the array. We can do this with the ``np.argpartition`` function:\n",
    "\n",
    "上面我们进行了完整的排序，事实上我们并不需要这么做。如果我们只是对最近的$K$个邻居感兴趣的话，我们可以使用分区来完成，只需要在距离平方矩阵中对每行进行$K+1$分区，只需要调用`np.argpartition`函数即可："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "K = 2\n",
    "nearest_partition = np.argpartition(dist_sq, K + 1, axis=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> In order to visualize this network of neighbors, let's quickly plot the points along with lines representing the connections from each point to its two nearest neighbors:\n",
    "\n",
    "为了展示最近邻的网络结构，我们在图中为每个点和它最近的两个点之间连上线："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXgAAAD7CAYAAABgzo9kAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjAsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+17YcXAAAgAElEQVR4nO3dd1xT1/vA8U8SpqJWEfesynWBq85WXICrzopbW0frrFW/Vquto1q19me1dVurrVpbLM46GS7cWwHHdY/WWcQtIEl+f4AUFCVAIECe9+vFC3NzcvM8Jjz35OTeczRGoxEhhBDZj9bSAQghhEgfUuCFECKbkgIvhBDZlBR4IYTIpqTACyFENmVj6QDi2AM1gZuA3sKxCCFEVqEDCgOHgaiX78wsBb4msNvSQQghRBZVH9jz8sbMUuBvAkREPMFgSNt5+c7OToSHPzZLUFmBteUL1pezteUL1pdzavPVajXkzZsT4mroyzJLgdcDGAzGNBf4F/uxJtaWL1hfztaWL1hfzmnMN8mhbfmSVQghsikp8EIIkU0lO0SjKMp04AOgFOCmqmpYEm10wCygGWAEvlVV9WfzhiqEECIlTOnBrwM8gKtvaNMNKAuUA+oCExRFKZXm6IQQQqRasgVeVdU9qqpeT6ZZJ2CRqqoGVVXvEntQ8DFHgEIIIVLHXGPwJUjcw78GFDfTvoUQQqRCZjlNEog9F9QcXFxymdTu5r9PWLvrAjuP/k1kVAwO9jY0rFGMdg3KUjh/TrPEkhFMzTc7sbacrS1fsL6c0yNfcxX4a0BJYi+XhVd79CYJD3+c5nNfXVxycffuo2TbhVwMZ966UPR6I/q453wWFUPAgatsO3yNgW3dcC/jnKZYMoKp+WYn1pazteUL1pdzavPVajVv7Biba4jGD/hYURStoiguQFtgtZn2bXZ3Ip4yb10o0c8N8cX9Bb3BSPRzA/PWhXIn4qmFIhRCiLRLtsArijJLUZS/gWJAkKIop+K2b1YU5Z24ZsuBS8B54AAwUVXVS+kUc5r5H7qOXv/mTwp6vZGAw8l9tyyEEJlXskM0qqoOAYYksb1Fgn/rgQHmDS397D91K1HP/fyhVTjlLUbhcnXit+kNRvaH3aK7t2KJEIUQIs0y1ZesGSUyOvG0DRcO+KGPiaJQ2dpUb/k5Wp1Nku2EECIrscqpChzsdIlu1+/2PXY58nDrwkECF/Yi4ub5JNsJIURWYpUFvm6lQui0mvjbTs7F8PxkCQXL1OJ55CP2/vE5Z3f/Sq3y+S0YpRBCpI1VFvimtYqj02kSbdNqddRsMwZ378FoNFouHF7HnAndOHPmtIWiFEKItLHKAl8gbw4GtnXDzlabqCcPUNrdC88+c8jvUoirVy7RuPG7/Pjj98TExFgoWiGESB2rLPAA7mWcmdi7Fg2qFsHRTocGcLTT0aBqEWZ+3p5DB4/RrFkL9Ho9kyd/TfPmjTl3TrV02EIIYTKN0ZgpVk0pBVzOyCtZTWE0Gvnpp3mMGzcGjUaDjY0NX3wxlgEDBqPTZY4vYK3tij+wvpytLV+wvpzNcCVraeDKK/enObJsTKPR0K/fINav30K+fPnQ6/VMnDiWVq2acuHCeUuHJ4QQbyQF3gR16tRjx459vPNOLQBCQ0/SqNG7LFgwB71ezpUXQmROUuBNVLBgIdas2Ui/foOIiorC0dGBcePG0LZtCy5dumjp8IQQ4hVS4FPA1taWSZOmsmjRr0RFRePklIvQ0BAaNarHzz8vwGAwWDpEIYSIJwU+Fdq0aU9AwE4KFSpEZOQzihYtzpgxI2nf/n2uXLls6fCEEAKQAp9qilIef/8dtGjRigsXzuHuXpWQkJM0bFiPJUsWSW9eCGFxUuDTIFeu3CxevIwJEyZz6lQozs7OVKpUmS+++B8+Pm24di3Fa54IIYTZSIFPI41Gw8CBn7J69QaePHlCWFgoPXp8xLFjR2nQoC7Llv1CJrnWQAhhZaTAm0m9eu+xbdtuKld2Y/nyX2nTph3VqlVnxIjP6NixLX//LYuHCCEylhR4MypcuAhr127i44/78/vvy4mOjmbs2K85fPgQHh51WLFimfTmhRAZRgq8mdnZ2TF58ncsWLCYsLAQFi6cxw8/zKVKlaoMGzaYLl0+4MaNfywdphDCCkiBTyft2/uwZct2nJycGDCgD97ezZgy5f84cGAfHh518PVdIb15IUS6kgKfjipUqEhAwE68vZszfvyXHDq0n40bA6lQoSJDhgygR49O3Lp109JhCiGyKSnw6Sx37jz8+usKvvrqa/76ax39+/dm+vQfmTRpKsHBO/HwqM2qVSulNy+EMDsp8BlAo9EwZMgw/PzWc+9eOM2aNaZIkWLs2LGXsmVdGTjwYz76qBt37tyxdKhCiGxECnwGql+/AUFBuylfvjx9+vRg+fKlrF27ifHjv2H79kA8PGqxdu0q6c0LIcxCCnwGK1KkKOvWbaFXr77MmzeLTp3a4ePTme3b91KqVGn69etNnz49uXv3rqVDFUJkcVLgLcDe3p5p02YwZ85Cjh8/iqdnfSIiIti4MZCvvvqagIAteHjUYsOGdZYOVQiRhUmBt6COHbuwefM2HBwcaNu2Ob/++jOffjqUoKDdFCtWgj59evLJJx8RHh5u6VCFEFmQFHgLq1SpMoGBu2jSxIsxY0YyYEAfihcvwebNQYwePZZNmzZQv34tNm3aYOlQhRBZjBT4TCBPnrdYuvQPxowZx7p1a2jRognXrl1h2LDPCQjYReHCRejVqxsDBvQlIuKepcMVQmQRUuAzCa1Wy9ChI/D1XcPt27fw9m7Epk0bqFSpMlu3bmfkyDGsX7+G+vVr4++/xdLhCiGyACnwmUzDho0JCtpN2bJl6dWrG5MmjUej0TBixBf4++8kf34XevToxODB/bh/P8LS4QohMjEp8JlQsWLF+esvf3r27M3s2TPp1Kkdd+/exc3NnYCAnQwfPpLVq//Ew6MOmzdvtnS4QohMyqQCryiKq6Io+xVFORf3u1wSbQooirJJUZQQRVHOKooyT1EUG/OHbB3s7e2ZPv0HZs2az+HDB/H0rM+RI4ews7Pjiy++YuvW7bz11lu0bNmSoUMH8fDhA0uHLITIZEztwS8A5qqq6grMBRYm0WYMcEZVVXfADagBtDdLlFasc+dubNoUhK2tHW3aNGfJkkUYjUaqVKlGYGAwo0ePxtd3BR4eddixY5ulwxVCZCLJFnhFUQoA1YE/4jb9AVRXFMXlpaZGIJeiKFrAHrADZOJzM3BzcycoaBcNGjTiiy/+x+DB/Xj69Cn29vZMmTKFzZuDcHJyolOndvzvf0N49OihpUMWQmQCmuTmPVEUpQawTFXVSgm2nQa6q6p6LMG2fMBqoCKQE5ijquoXJsZRCricstCtj8FgYPLkyYwfPx43NzdWr15N2bJlAYiMjGT8+PFMnz6dYsWKsWTJEpo0aWLhiIUQGaQ0cOXljeYcI/cBQoAmQC5gi6IoHVRVXWXqDsLDH2MwpG2iLReXXNy9+yhN+8jM+vcfiqtrJQYM6EuNGu/w22/LqVOnIQAjRnxFgwZeDBkyAE9PTz76qA/jxk3CycnJskGbWXZ/jV9mbfmC9eWc2ny1Wg3Ozq//+zZlDP46UFRRFB1A3O8icdsT+hRYoaqqQVXVB8B6oFGKIxbJatzYi8DAYEqVKk3r1q2ZOnUier0egJo1a7N9+1769x/M0qVLaNiwLnv37rZwxEIIS0i2wKuqegc4AXSJ29QFOK6q6svTHV4GmgEoimIHeAJh5gtVJFSiREk2bgygT58+zJw5nc6d28fPWePo6MjEiVNYv34rOp2Odu1aMmbM5zx58sTCUQshMpKpZ9H0Bz5VFOUcsT31/gCKomxWFOWduDZDgfqKooQSe0A4Bywyc7wiAQcHB37++WdmzJjNgQP78PLy4Pjxo/H316lTl+3b9/Lxx/35+eeFNGpUjwMH9lkwYiFERkr2S9YMUgq4LGPwKfci35Mnj9O7dw9u377FlCn/R48eH6HRaOLb7du3h88+G8i1a1f55JMBjB49jhw5clgw8tSz1tfYmlhbzmYYg0/yS1a5kjWbiD0vfhfvvlufESM+47PPBvLs2bP4++vVe48dO/bRq1dfFi6cR+PG73Lo0EELRiyESG9S4LORfPmc+f33Vfzvf6Pw9V1By5ZeXLny39mnTk5OfPvt96xevYHnz5/TqpU3EyZ8lehAIITIPqTAZzM6nY5Ro77k99/9uH79Gl5eDQgK8k/Upn79BuzatZ8ePXoxb94sPD3rc/ToYQtFLIRIL1LgsylPz6YEBu6iePESdO3qw7Rpk+NPpQRwcsrF9Ok/sHLlWp4+fUrLll5MmjSeyMhIC0YthDAnKfDZWKlSpdm0KZDOnbvx/ffT6NbNh3v3Ei//16hRE3bt2k/Xrj2YPXsmXl4enDhx7DV7FEJkJVLgszlHR0d+/HEe06f/yJ49wXh5NeDkyeOJ2uTOnYcZM2bzxx+rePjwIc2bN2Hq1IlERUVZKGohhDlIgbcCGo2Gnj17sWGDPwaDgfff92bFimWvtGvSxJvg4AP4+HRm5szpeHs3JCTkhAUiFkKYgxR4K1KtWg2CgnZTp049hg0bzLBhg18Zc8+T5y1mzZrPb7+t5N69cJo1a8x3300hOjraQlELIVJLCryVcXZ2xtd3DcOGjWDFimW0atWUa9euvtLO27s5wcEHaNv2A6ZP/5ZmzRoTFhZqgYiFEKklBd4K6XQ6Ro8ex/LlK7l8+RJeXh5s3x74Sru8efMxb94ifv31d27duknTpg35/vtpPH/+3AJRCyFSSgq8FWvatDkBATspXLgoXbp04Pvvp2EwGF5p16LF++zefYj332/NtGmTad68CWfOnLZAxEKIlJACb+XefrsMmzcH8cEHHZk2bTI9enTi/v2IV9o5OzuzcOEvLF68nBs3/sbLy4Mff/yemJgYC0QthDCFFHhBjhw5mDv3J7799nt27tyOp2cDQkNPJtm2Vas2BAcfomnTFkye/DUtW3py7pyawRELIUwhBV4AsadS9u79MevXb+H582hatvTC13dFkm3z58/P4sXLWLToV65evUKTJu8xZ86Pia6UFcJS7kQ8Zbm/ysAZu+j97XYGztjFcn+VOxFPLR1ahpMCLxJ5551aBAXtpmbN2gwZMoARI4a+9oKnNm3aExx8iCZNvJk4cSzvv+/NhQvnMzhiIf4TcjGccUsOEXzyBpHRsR2OyGg9wSdvMG7JIUIuhiezh+xFCrx4hYuLCytXrmXIkOEsW7aE1q2b8vffL6/QGKtAgQL88stvzJ//Mxcvnqdx43dZsGCO9OZFhrsT8ZR560KJfm5A/9K6EnqDkejnBuatC7WqnrwUeJEkGxsbvvpqAr/++jsXLlzA07M+u3btSLKtRqPhgw86snv3IRo0aMS4cWNo06Y5ly5dyOCohTXzP3Qdvf7NCwbp9UYCDifdWcmOpMCLN2rR4n0CAnZQsGAhOnVqxw8/TE/yVEqAggULsWyZL3PmLERVz9Ko0bssWjT/te2FMKf9p24l6rlv/tEH//k9E73/9AYj+8NuWSI8i5ACL5JVpkw5Nm/eRtu2HzBlykQ+/LALDx7cT7KtRqOhY8cuBAcf4N136/Pll6No165looVHhEgPL8bc/6Ph+bOHBMzrjiEm+g3tsi8p8MIkOXPmZP78n5ky5Tu2bQvEy6sBp06FvbZ94cJFWLHCjx9/nEdYWCgNG9Zj8eKfpDcv0o2DnS7Rbc9+v4JGS0z0UwIWfEhM9NMk22VnUuCFyTQaDX379mfdui1ERkbSokUT/Px839i+S5fuBAcfoFat2owePYIOHVonOfeNEGlVt1IhdNr/Fpq3c8iB58c/g0ZDTPQzAhf25vnT+9StXMiCUWYsKfAixWrVqk1Q0G6qVavBoEGfMGrU8DfONlm0aDFWrlzLjBmzOXHiOA0a1GXp0iUYjW/+QkyIlGhaqzg6nSbRNgenfNTvPhMA/fNIAhd9QoUC1nP1tRR4kSoFChRg1aq/GDhwCL/88jNt2jTnxo1/Xtteo9HQvfuH7Nq1n+rV3+Hzz4fSsWPb155+KURKFcibg4Ft3bCz1SbqyedxKUXtD8YBYNBH07qlBydOHH/dbrIVKfAi1WxsbJgw4RsWL17G2bNn8PSsz+7du974mOLFS7Bq1Xq++24mhw8fwsOjDitWLJPevDAL9zLOTOxdiwZVi+Bop0MDONrp6NSuFRMmfQ/A8+fPad68MTt3brdssBlAk0n+sEoBl8PDH2MwpC0eF5dc3L37yCxBZQWZJd/z58/Rq1c3Llw4z5dfTmDw4M/QaDRvfMzVq1cYOnQQe/fupnFjT2bMmE2RIkWTfa7MknNGsbZ8If1ynjJlIj/8MB2I/VQ5f/7PtG/vY/bnSanU5qvVanB2dgIoDVx55f40RyYEUK6cK1u37qBVq7ZMmjSOXr268/Dhgzc+pmTJUqxevYGpU/+PAwf24eFRB1/fFdKbF+lmzJhx8QXdaDTSv38ffv55gYWjSj9S4IXZODk58dNPvzBp0lT8/Tfj7d0w2XnjtVotffr0Y/v2vVSoUJEhQwbQvXtHbt26mUFRC2uzYMFiateuC8T24seMGcnUqd9YOKr0IQVemJVGo6Ffv0GsXbuJx48f07x5Y9as8Uv2cW+/XYb167cwadJU9uwJpn792vj5+UpvXqSL9eu3ULr02xiNRnQ6HTNnfsfw4UMsHZbZSYEX6aJOnXps27YbN7cq9O/fhy+/HJnswt1arZZ+/QaxffseXF0VBg36hA8/7Mrt27czKGphLbRaLTt27CNfvnzo9Xrs7R347bdf+fDDLpYOzaykwIt0U7BgIdas2Ui/foNYtGgB7dq1NGnopUyZcvz111YmTJjMjh1BeHjUYu3aVdKbF2aVI0cOdu06iKOjI1FRkeTOnYctWzbRqlXTbHPFtUkFXlEUV0VR9iuKci7ud7nXtOuoKEqooihhcb8LmjdckdXY2toyadJUFi36lVOnwmjSpD779u1J9nE6nY6BAz9l+/a9vP12Gfr1602fPj25e/duBkQtrEXBggXZsmUHOp0NDx8+oHDhohw8uJ8GDeok+4kzKzC1B78AmKuqqiswF1j4cgNFUd4BJgBeqqpWBt4D3nwahbAabdq0x99/B3ny5OGDD1oxb95sk3rk5cq5smFDAGPHTiQgYAseHrXw80t+TF8IU1WsWJHff/8TjUbDnTu3qFixEqp6ltq1q/L48WNLh5cmyRZ4RVEKANWBP+I2/QFUVxTF5aWmw4DpqqreAlBV9YGqqpHmDFZkbYpSHn//HTRv/j4TJnxJ374f8vhx8uf+2tjY8OmnQwkK2k3x4iXo2LEjn3zyEeHh1rU6j0g/jRp58v33sctOXrlymfr1G/LPP39To0blLP2p0ZQefHHgH1VV9QBxv2/EbU+oIvC2oijBiqIcUxTlK0VR3nyli7A6uXLlZvHiZYwf/w2bN2+gadNGJi/aXb58BTZv3sbkyZPZtGkD9evXYtOmDekcsbAW3bt/xLBhI3n69CmnT4fh49OZiIh71KrlzuXLlywdXuoYjcY3/ri6utZwdXU99dK2066urtVf2hbq6ur6l6urq72rq2suV1fXva6urj2T23/cTymjsDo7d+40FihQwJgzZ07jypUrU/TYkydPGqtVq2YEjF27djX++++/6RSlsDZdu3Y1AkZXV1fj559/bgSM9vb2xqNHj1o6tDcpZUyitiY7VUHcEM05wFlVVb2iKDogHCinqurdBO02An+qqros7vZIoISqqoNNOM6UQqYqSJWsnu/Nmzfo2/dDDh8+SL9+gxg3biK2trZvfMyLnJ8/f86PP37PjBnfkS+fM9On/0izZi0yKPKMk9Vf49SwdM6tWjXl4MH91K37Ls2atWT8+DHodDp8fdfQoEEjsz+fxaYqUFX1DnACeHGCaBfgeMLiHud3wFtRFI2iKLZAE+BkiiMWVqVw4SKsXbuJjz/uz8KFc/ngg1bcvm3akmq2traMGPEF/v47yZ/fhZ49OzN4cD/u349I56hFdhd7IVQZ9u/fy6lTocyZswCDwUDHjm1Zu3Y1dyKestxfZeCMXfT+djsDZ+xiub+a6Rb0NvUsmv7Ap4qinAM+jbuNoiib486eAfAF7gCniT0gnAIWmzdckR3Z2dkxefJ3LFiwmJCQEzRpUp8DB/ab/Hg3N3cCAnYyfPhIVq/+Ew+POgQF+adjxCK7i70Qai/58jnz559/cPnyJVas8Iu7GK8X3QaNI/jkjfjl/yKj9QSfvMG4JYcIuZh5vvyX2SSzuOyW75kzp+nVqxvXrl1l/PhJfPLJwFdmpXxTzidPHmfIkAGcOXOaLl26M2nSVHLnzpMRoaeb7PYamyKz5Hz79m1q1XLn2bNnzJw5hwJFS9OjcxsMhhjK1emIUq/rK4+xs9UysXctCuTNYfLzyGySwipUqFCRgICdeHk1Y+zY0fTr1ytF5yJXqVKNgIBdDB06gpUrf8fDow7btwelY8QiO3txIZSNjQ3Dh3/KriOXaPjhLHQ29pw/8CchgfNeeYxebyTgcOZYyEYKvMh0cufOw6+/ruCrr77mr7/W0bx5Y86fP2fy4+3t7RkzZhybNwfh5ORE587t+d//hvDo0cN0jFpkV7EXQq0CYNH0ocTEPKd2h4lodXZcCw0gePmwRO31BiP7w0z7Him9SYEXmZJGo2HIkGH4+a0nPPxfvL0bsmHD+hTto3r1dwgK2s3gwUNZsWIZDRrUZdeuHekUscjOGjZszOTJ0zAa9AT/NpR9vqMw6GOnMnh49zIP7iQ+T/7F2LylSYEXmVr9+g0ICtpN+fLl6dOnBxMmfEVMjOmLJjs4ODBu3EQ2bPDH3t4eH582jBw5LMtfgi4yRnR0NFu2bKJPn558/fXY2I1GIzobezw+nE2t9rFrvR5aOynRBGUOdjpLhPsKKfAi0ytSpCjr1m2hV6++zJs3Cy8vL+7cuZOifdSsWZvt2/fSv/9gli5dQsOGddmzJzidIhZZmdFo5MiRQ4waNRx3d1c+/LAL+/fvoWfPXgz9eilFKzRAHxPF0fVTyF+iKgVKv0PUkwjO7FoCgE6roW7lQhbOIpYUeJEl2NvbM23aDObMWcjBgwfx9KzPoUMHU7QPR0dHJk6cwvr1W9HpdLRv/z6jR4/gyZMn6RS1yEouX77E9OnfUrdudVq08OSPP37Dw6MhK1b8ycmTKpMnf0ffzk2p3fp/5CtaiSf3b3LAbyzVW41EZ2PP5eObeBR+HZ1Og3fNl2dysQw5TTKLs7Z8AW7evEybNm35++/rTJo0ld69P0l2ge+XPX36lClTvuann+ZTsmQpZs9eQJ069dIp4rSxxtc4o3KOiLjH+vVr8fPz5fDhg2g0Gt59tz4+Pp1p2bJVkqfYhlwMZ86akwQuGsiT+zcoWr4BhcrV4eiGaTjmdmGD/yHcyzinKA45TVKIOO7u7gQG7qJJEy9Gj/6cAQP6prgXniNHDr75Zhrr1m0GoE2b5owd+wVPn2auKxGF+UVFRbFx41989FE33NxcGTlyGA8fPuCrryZw7Ngp1qzZSJcu3V97/YR7GWe+6VuHsdNXYueYm3/O7uJp+BXKVnyHZw/vsnHl3AzO6PWkB5/FWVu+8F/OBoOBWbNmMHXqJMqXr8Avv/zG22+XTfH+Hj9+zDffjGfJkkW8/XYZZs1aQK1atdMh8tSx5tfYXIxGI4cOHcTPz5e//lrD/fv3cXEpQPv2PnTs2JnKld1T/CkQXlwIVYVnz54ybdoMxo0bw/Pn0Rw+fJLixUuavB/pwQvxEq1WG3dB01pu376Fl1dDNm/emOL9ODk58e2337NmzUZiYmJo1cqb8eO/5NmzZ+kQtchIly5d4Ntvv6FmzSq0auWNn98fNG7sha/vak6ePMukSVNxc6uSquIOsRdC+fvHXgj1xRf/4+OP+2MwGPDxaWvmTFJHCrzI8ho2bExQ0G7KlCnDRx915ZtvJqToVMoX3nvPg50799GzZ2/mz59NkybvcfToYbPHK9JXeHg4ixf/RPPmjalTpzozZ/4fpUqVZvbsBZw6dYEFCxbTuLEXNjY2Znm+8uUrxF8ItWDBHCpWrMSlSxeZNWuGWfafFjJEk8VZW77w+pyjoqL48stRLFu2hPr1G7BgwRJcXF5eeMw0O3duZ9iwwdy8eYNBgz7j889H4+DgkNbQU0Ve4+RFRkYSELAFPz9ftm0LJCYmhooVK+Pj05n27TtQuHCRdIw21h9/LOezzwbh4OBATIweo9HA8eOnKVSocLKPlSEaIZJhb2/P9Ok/MGvWfA4fPoiXl0eqe+ANGzZm1679dO3ag9mzZ+Ll5cHx40fNHLFIC4PBwL59exg+/FMqVy5H374fcvLkCT75ZCA7duxj5859DBo0JEOKO0CXLj0YMeILIiMjsbOzQ6/X06lTuwx57teRAi+ync6du7FpUxA2Nra0bt2MX3752aQFvl+WO3ceZsyYja/vah4+fEiLFp5MnTqRqKiodIhamOr8+XNMmTKRmjXdadu2BWvWrKJZsxb4+a3n+PHTTJjwDZUqVbZIbCNHjqFjxy48ffoEOzs7zpw5zeLFP1kkFpAhmizP2vIF03O+fz+CgQM/JigogI4du/DddzPJkcP0KVwTevDgPmPHjsbXdwUVKlRi9uz5uLtXTdW+UkpeY7h79y7r1q3Cz8+XEyeOo9VqadCgET4+nWne/H1y5sxpwWhf1aZNc/bv3wvELhofGnoOZ+f8r20vQzRCpNBbb+Xlt9/+ZNSoL/Hz86VFC89UL56cJ89bzJo1nxUr/uTevXCaNWvMtGmTiY6ONnPU4oVnz56xdu0qunbtgLu7K19+OQq93sDEiVM4eVJl5cq1dOjQKdMVd4C1azdRpkzsKbsxMTF06dLBInFIDz6Ls7Z8IXU5b98eyIABfdHrDcyd+xNNmzZP9fPfvx/Bl1+Ows/Pl0qV3Jg9ewGVK7ulen/JsabX2GAwsHfvbjZuXIOf3yoeP35EkSJF+eCDjvj4dKZ8+QqWDtFkkZGRVKtWkfDwfwHo1Hcc+vw1iYzW4zneeykAACAASURBVGCno26lQjStVZwCeXOkWw9eCnwWZ235QupzvnbtKr179yAk5ATDho1g5Mgv0elSP+vfli2bGDHiMyIi7vG//41iyJDhyS4YnhrW8BqfPXsGPz9fVq/+kxs3/iFXrly8/34bfHw6U6/ee2i1WXOw4e7du1SrXonoqEg0Gi1eA37DziF2mFCn1aDTaRjY1o0mdUrJEI0QaVGiREk2bgygW7eezJw5nc6d2xMenvr1M5s3b8nu3Qdp3bot06ZNpnnzJpw5c9qMEWdvt2/fZv78OTRu/B4eHrWZN28WlSpVZuHCJdy6dYsff5zHe+95ZNniDmC0yUn9btMBDUajgX0rv4i/T28wEv3cwLx1odz8N30mvMu6/3NCpIKDgwMzZ85hxozZHDiwL82nP+bL58yCBUtYvHg5N278jadnfX788ftUXWhlDZ48ecKqVSvp1KkdVaoojB8/BhsbHZMnTyMk5BwrVvjRrl2HVH8Zntn4H7qOU77i1P5gAgCPw69x4ci6RG30eiPrgy+ky/NLgRdWqXv3D9m4MQCNRkOrVk1ZtuyXVJ1K+UKrVm0IDj5E8+bvM3ny17Rs6YmqnjVjxFmXXq9n587tDBr0CZUqlWXgwI+5cOE8n302nL17jxAQsIuPPx6Q6ovSMrP9p26hNxhxKVkF5d3uAJwNXpqojd5gZMfRv9Pl+c1zra4QWVCVKtUIDNzFgAF9GTHiM44ePcy3336Po6NjqvaXP39+fv55KevXt2HUqOF4etZn1KivGDBgcJrG+rOqU6fC8PPzZc0aP27duknu3Hlo374DPj6dqV27bpYeejFVwqX7ytXuwJMHt3h4++Ir7Z5Fpc8nPinwwqrly+fM77+vYvr0b/n++2mEhYWyePEySpUqnep9tmnTnrp132PkyGFMnDiWTZv+YvbsBZQtW86MkWdON2/eYPVqP/z8fDlz5hQ2NjZ4enrj4zMNL69mFpvuwVIc7HSJinxV78FJtnO0T59SnP0PoUIkQ6fTMWrUl6xY8SfXrl3F27sBQUH+adpngQIF+OWX31iwYDEXL56nceN3mT9/Dnp95liM2ZweP37EypW/06FDG6pWrcDEiWPJkcORqVOnExp6nmXLfGnVqq3VFXeAupUKodO+eaZKnVZDoxrF0uX5pcALEcfLqxmBgbsoVqwE3bp1ZNq0yWkqyBqNhvbtfdi9+xANGjRi/PgxtGnTnEuX0ucLtYwUExPD9u2B9O/fh8qVy/Hpp/25cuUyw4ePZP/+o2zZsp0+fT7B2TllKxtlN01rFUenS6bA6zS08Uj5OgamkAIvRAKlSpVm06ZAOnbswvffT6NbNx8iIu6laZ8FCxZi2TJf5sxZiKqepVGjd/npp3kYDAYzRZ0xjEYjISEnGDt2NFWqlKdz5w/Yvj2QDh06s2FDAIcPn2TUqC8pUyb7D0WZqkDeHAxs64adrfaVnrxOq8HOVsvAtm4Uzp8+V+PKhU5ZnLXlCxmTs9FoZNmyX/jyy5EUKlSYJUuWm2XumVu3bjJ8+KcEBQVQt+67/PDDXEqXfvuNj7H0a/zPP3+zevWf+Pn5oqpnsbW1xcurGT4+nfH09Mbe3t7sz2npnM3tTsRTAg5fZ3/Yrf+uZK1cCO+aciVrimS3N0ZyrC1fyNicjx8/Su/ePfj337tMmzaDrl17pHmfRqORlSt/j5tbJYaxYyfSq1ff155VYonX+NGjh2zYsB4/P1/27duD0WikVq06dOjQiTZt2pE3b750fX5re1/LZGNCWEC1ajUICtpNnTr1GDp0EMOHf0pkZGSa9qnRaOjcuRvBwQeoXbsuo0ePoEOH1ly7dtVMUafO8+fPCQzcyieffESlSmUZOnQQN278w+efj+bQoZNs3BjARx/1SffiLsxHTpMUIhnOzs74+q7hu+8mM3PmdEJDQ1iyZDn2TvnxP3Sd/aduJTmBVHKKFi2Gr+8aVqxYxrhxY2jQoC4TJnxDz569Ur1GaEoZjUZOnDiGn58v69at5t9//yVfvnx07dqDDh06UaNGzQyLRZifSUM0iqK4AksBZyAc6Kmq6vnXtFWA48A8VVVHmBhHKWSIJlWsLV+wbM7+/lsYNOgTjGhwbzqU/CWroU/wnk04gZR7GdPPILl+/RpDhw5m9+6deHg04ocf5lCsWHEgffK9du1q/Lj6hQvnsbe3x9u7OT4+nWnc2BM7OzuzPl9KWdv72tJDNAuAuaqqugJzgYVJNVIURRd337qk7hciq2vatDm+q7aitX+LvX5fc2afL0bjf2fDJJxA6k7EU5P3W7x4CVatWs93383kyJFDeHjUYcWKZWmaPuFlDx7cZ/nyX2nduhnvvOPG1KmTcHEpwIwZswkLO8/ixcto1qyFxYu7MJ9kh2gURSkAVAe84jb9AcxRFMVFVdW7LzX/AtgIOMX9CJHtnLltw3tdv+NEwFzO7fuD+zfPU7X5UOwc/nvL6/VGAg5fp7u3YvJ+NRoNH33Uh0aNmjBs2GCGDRvMhg3rWLr0F+zt8wCxZ2OkZFgoOjqabdsCWbVqJQEBW4iKiqJs2XKMHj2WDz7oSIkSJdP+HyIyLVPG4IsD/6iqqgdQVVWvKMqNuO3xBV5RFHegKdAIGJsOsQqRKew/dQuNzo6qzYaSt7BC2I6fCZjXHfuc+XBwykeOPAVxyleUOxfK0LhyT4oUKZqi/ZcsWYpVq/7il19+ZtKkcVSuXJlJk76lwjtNmb8+DL3eGD8sFBmtJ/jkDfaG3YwfFjIajRw9ehg/P1/Wr1/DvXv3yJ8/Pz179sLHpzNVqlSTcXUrkewYvKIoNYBlqqpWSrDtNNBdVdVjcbdtgT1AL1VVTyuKMgFwSukYfMrDFyLjtf7fehL+1RxeP5XbFw+i0WgTDde8oNFosLe3J0+ePBQoUIASJUrg6uqKm5sbNWvWpGLFiq89RfLixYv06tWL3bt3U6jMO1RuMhAHp6TPYnn++A5uea+yfs2fnD9/HgcHB9q2bUv37t3x9vZOl8VIRKaRuvPg44ZozgHOcb13HbFftJZ7MUSjKEoJ4BjwOO5hbwEaYKWqqp+YEFwp5EvWVLG2fMHyOQ+csSvRBFK7V/wPrc6OdztPxWCI4dG/13hw6wJP71+nZJ5I/vnnb/79918ePXpIVFRUkvu0tbXFycmJfPmcKVy4CKVKvU358hVwd69Co0bv0n3AeDb6zkGrs6VSo74UrdAQjUZD9LNH3Dy3l7/P7CTixlk0Gg3vvlsfH5/OvP9+a3Llyp1R/y1mZenXOKOl15esyQ7RqKp6R1GUE0AX4Le438cTjr+rqnoNiF8yPBU9eCGyjLqVChF88gZ6g5HIx/d4cPsi5d+LvQBKq7UhT4G3yVeoDA2qFklyDP769ascO3aUU6fCuHDhPNevX+Pu3Tvcvx/BpUuXuHjxAnv2BCd6jEajRWtjhz4mmhNbf+TUrl/I41Ka8L9PYTTE4ORcnPLv9aCMeyN+mWCZBZ5F5mPqefD9gaWKoowDIoCeAIqibAbGqap6JJ3iEyLTaVqrOHvDbqI3GLlzOXY1qAKlayRqo9Np8K5ZPMnHFy9ekuLFS9KmTfsk74+IuMeJE8cIDQ3h3DmVGzeucyz0AtHPHmIwRAPw/NlDwv8+RamqLShWsSG5XUqj0WiQkXWRkEkFXo1dmqZ2EttbvKb9hLSFJUTm9WICqXnrQrlz+QiOuVzIlT/2bJSE58GbcrFTUvLmzUejRp40auQJxH589xm9MX5YyBATzYO7V8hdoDQ6XeJxdQc761tYRLyeTFUgRCq4l3Hmy27u3LseQpFyNdFqNDja6WhQtQgTe9dK0UVOpkg4r7jWxo68hV1fKe46rYa6lQuZ9XlF1iZTFQiRSudPHyM66hnffN6bJk0ap+tzJRwWep03DQsJ6yQ9eCFSKTBwK46OjtSrVz/dn8vUecVTOywksifpwQuRCkajkcBAfzw8GqZ6ke6Uci/jzMTetd44r7gQCUmBFyIVzp1TuXbtKkOGDM/Q5y2QNwfdvZUUTYEgrJcM0QiRCgEBWwHw8mpq4UiEeD0p8EKkQmDgVipXdqdw4SKWDkWI15ICL0QKRUTc49ChA3h7S+9dZG5S4IVIoe3bgzAYDHh5NbN0KEK8kRR4IVIoMNCf/PnzU61ajeQbC2FBUuCFSIGYmBi2bw+kSRPv107xK0RmIe9QIVLgyJFD3L9/H29vGZ4RmZ8UeCFSICBgKzY2NjRsmL5TEwhhDlLghUiBoCB/6tZ9L8supCGsixR4IUx09eoVzp49g5eXt6VDEcIkUuCFMFFQkD+AjL+LLEMKvBAmCgjYSpkyZXn77bKWDkUIk0iBF8IEjx8/Zu/e3XJxk8hSpMALYYLdu3cRHR0tk4uJLEUKvBAmCAzcSq5cualdu66lQxHCZFLghUiGwWAgMNCfRo2aYGdnZ+lwhDCZFHghkhEaepLbt2/J8IzIcqTAC5GMwEB/NBoNTZrI+e8ia5ECL0QyAgO3Ur36O+TPn9/SoQiRIlLghXiD27dvc/z4Mbm4SWRJUuCFeINt2wIA5Px3kSVJgRfiDQID/SlSpCiVKlW2dChCpJgUeCFeIyoqip07t+Pp2RSNRmPpcIRIMSnwQrzG/v17efLksSyuLbIsKfBCvEZg4FYcHBx4770Glg5FiFSRAi9EEoxGIwEBW6lfvwE5cuSwdDhCpIqNKY0URXEFlgLOQDjQU1XV8y+1GQt0BmLifsaoqupv3nCFyBgXLpzn6tUrDBw4xNKhCJFqpvbgFwBzVVV1BeYCC5NocwioqapqFaA3sFJRFEfzhClExgoI2Aog0xOILC3ZAq8oSgGgOvBH3KY/gOqKorgkbKeqqr+qqk/jboYAGmJ7/EJkOYGBW6lYsTLFihW3dChCpJopQzTFgX9UVdUDqKqqVxTlRtz2u695TE/goqqqf6ckGGdnp5Q0fy0Xl1xm2U9WYW35QvrmHBERwcGD+xk1alSm+b/NLHFkJGvLOT3yNWkMPiUURWkATAK8UvrY8PDHGAzGND2/i0su7t59lKZ9ZCXWli+kf87r1q1Hr9dTr16jTPF/K69x9pfafLVazRs7xqaMwV8HiiqKogOI+10kbnsiiqLUBX4D2qqqqqY4WiEygYCAreTLl48aNd6xdChCpEmyBV5V1TvACaBL3KYuwHFVVRMNzyiKUhNYCXRQVfWYuQMVIiPo9Xq2bQugSRNvdDqdpcMRIk1MHaLpDyxVFGUcEEHsGDuKomwGxqmqegSYBzgCCxVFefG4Hqqqhpo3ZCHSz5Ejh4mIiJDZI0W2YFKBV1X1LFA7ie0tEvy7phnjEsIigoL80el0NGzY2NKhCJFmciWrEAkEBGylTp165MnzlqVDESLNpMALEef69WucOXNK5n4X2YYUeCHiBAbGzqwh4+8iu5ACL0ScwMCtlCpVmjJlylo6FCHMQgq8EMCTJ0/YsycYb+9msriHyDakwAsB7NkTTFRUlIy/i2xFCrwQxJ49kzOnE3XrvmvpUIQwGynwwuoZjUaCgvxp2LAxdnZ2lg5HCLORAi+sXlhYKDdv3pCzZ0S2IwVeWL3AwNjFPZo08bZwJEKYlxR4YfUCA7dSvXoNChQoYOlQhDArs88HLzKPOxFP8T90nf2nbhEZrcfBTkfdSoVoWqs4BfLKQtIAd+7c4dixo4wcOcbSoQhhdlLgs6mQi+HMWxeKXm9EH7eISmS0nuCTN9gbdpOBbd1wLyMrKm7fHojRaJS1V0W2JEM02dCdiKfMWxdK9HNDfHF/QW8wEv3cwLx1odyJePqaPViPwEB/ChUqjJtbFUuHIoTZSYHPhvwPXUev/6+wG41Gnj9/nqiNXm8k4PAri3JZlejoaHbs2IaXV1O5elVkSzJEk83o9Xr8dx3izt/neXDnEg/uXOTe36fi7tXg4JSPohUaUrJKM/aHaenurbxxf9nZgQP7ePz4kVy9KrItKfBZWFRUFMeOnSc4eD8hIScICTnJ6dNhPHv2DACtzo7cLqXIU6gcD29fxGg0EPk4nIuHV3Px8GrQaDj659t4eDSkfXsfatWqg1ZrPR/qAgO3Ym9vT/36DSwdihDpQgp8FvHkyRNOnw4jJOQkYWEhhISc5OzZ0/FDL05OuXBzc6dnz14c+8cex3ylcMpXDK32v3VFY6IjuXBoFdfCgoh+eh+MRi5dusilSxf59dfFaDQaChcuQtWq1WjR4n1at26Pg4ODpVJOd4GB/rz7bn1y5sxp6VCESBcao9GYfKv0Vwq4HB7+GIMhbfG4uOTi7t1HZgnKUh48uE9YWCghIScJCTlBaOhJLlw4j8FgAMDZ2Rk3tyq4uVXhvffqULKkK6VKlY7vfS/3Vwk+eeOVL1gT0qAnx8PjnDu6mZCQk+j1+iTb5cmTh/LlK9KoURM6depC0aLFzZ9wCpnjNb548Tx169Zg6tTp9OnziZkiSx/Z4T2dUtaWc2rz1Wo1ODs7AZQGrrx8v/TgLezu3buEhp4gNDQkvqBfvXol/v7ChYvg7l6F1q3b4e5eFTc3d4oUKRr/pWBSb4ymtYqzN+zmGwu8ra0tYz8fTIG8IzEYDAQEbGXRovkcOXIofohHo9Hw8OFDDh7cz8GD+/n222+wt7enZMnS1K1bj3btOlCnTr0sOawTEBC7uIecHimyM+nBZxCj0ciNG//EF/EXwyw3b96Ib1OqVGnc3Krg7l4lvofu4uLyxv2+Lt+kzoMH0Gk16HSaN54Hf+DAPubPn82ePbt59OghAFqtFkdHRwwGQ/wB4MX2QoUKxw/rvP9+W3LkSN+LqMzxGrdv/z7//nuX4OCDZooq/WTW93R6srac06sHLwU+HRgMBq5cuZSoVx4WFkJ4eDgQWxTLlXONL+Lu7lWoXNktVQs9vynfOxFPCTh8nf1hCa5krVwI75qmX8l69uwZ5sz5gW3bAgkP/xeI7dkXKFCQt956i0ePHnH79q1EQzzpPayT1tf44cMHlC9fmgEDPmXs2K/NGFn6yAzv6YxmbTlLgTdRRr8xYmJiOH/+XKJeeWhoCI8fx8Zga2tL+fIVE/TK3alYsbLZvtjLyHxv3PiHuXN/ZNOmDdy48U/89mLFilOzZm1y5MjB8ePHuHz5YqJevrmHddKa819/raVv3w/56y9/6tSpm+r9ZBRrK3ZgfTlLgTdRer4xoqKiOHv2dFyv/CRhYSc5dSqMyMhIABwdHalUyQ03N3fc3avi7l4FRamQrnOMW+oP4f79+/z00zzWrl3FpUsXefE+cnEpgKdnU7p06cGRIwfZti2A06dPERFxL/6xWq2WggULUbVqNZo3f5/WrdulaFgnrTkPHtyPwMCtnDp1ERubzP81lLUVO7C+nKXAm+BOxFN2hd5ix5HraZ5c6/Hjx5w6FUZY2Mn4gq6qZ4iJiQEgd+48uLm5x/fK3d2rUrZsOXQ6XTJ7Nq/M8IcQGRnJsmW/4Ov7G2fOnI4frsmdOw8eHg0ZNGgIbm5V2LJlIxs3/sWxY0e4ceOfRMM6uXPnoXz5CjRq1JiOHbtQvHjJ1z5fWnLW6/VUrlyWBg0as2DB4lTtI6Nlhtc4o1lbzlLgk5GWLxXv34+IHy8PDT0Zf1rii/+b/Pnzx42VV40failZslSmuLw9s/0hGAwGVq/+k6VLl3DixDGio6MBcHTMQa1atenXbxCenrHzrh8/fpTVq/3Ysyf4lWEdGxs7HPMUJG+RCpRya0irpk1oXqckBfLmSFPOhw8fpGVLLxYsWEz79j5pTzgDZLbXOCNYW85S4N/gTsRTxi05RPRzw2vb2Nlqmdi7FsboR4l65aGhIVy7diW+XdGixRL1yt3dq1CoUOFMUcyTktn/ELZtC+Snn+Zx8OB+nj6NndzM1taOKlWq8tFHvenQoXP8ePzt27eZtWAxazds4sGdKzyPTJCXRoNDzrxUq1aDj3t1oXHjFiYP6yScNvnEjmVcPLSaifMCaNe4cpaYNjmzv8bpwdpylgL/Bkld2GM0Gnn26C4Pbl/i4Z1LPLx7iWf3rvDw/r/xbUqXfjvu3PIq8cMt+fPnN0M6GScr/SEcP36UuXNnsWvXDh48uA+ATqdDUSrQqVNXWrbtypTfQ+IP1IaYaG5dPMTN8/u5f+sckY/CMRr/O4jnzp0bRalAw4axwzolS5Z65Tlf/mQXvHwoNnY5qd9lSrKf7DKLrPQam4u15SwF/g0GzthFZPR/47l7fh/Bg9uXEhUDna0DdvY5KFE09vS+t97Ki4ODAzqdFq1Wh42NDTqdDq1Wh06nRafTJbj94n5t/O2E9+l0WmxsbBLdF3u/NtFtnc4mvn3ix+viYkhq37pEz/tynAULvkVExNNE92u12kz7ieOFixcvMGfODwQG+nPnzu24rRpyvlWIIsp7lK7RBjsHp1ce9/DORWwijnL7SgiXLiUe1rGzs6dkyZLUrl2Pdu0+oFzFGkz49Uj8AePZo7tsW/Qx5ev3pGzN9rGPiftkl5l78tZW7MD6cpYrWd8gYXEHsLHLgV2Ot7CxdUBna4/WxhaMRoxGA7a2tjx8+JD79yPQ6/VxPwb0+pj42wZDwu2xt2NiYu/PJAfEZCU8uLzpQJTUAe3FwSypg9CLfbzpIPTfwSypGF48nw3FihWnb99+PH36jIMH93Pk+Ame3L/J+YN+nD/oh84uB45OzjgXr4zOxg6drT06G3scHZ3o27c/OXLk5PnzaA4fPsjJk8e5dOkS58+f4/z5c/z2269oNBrsc+QlT8EyFCxbG31U7MGg4Ns14/+fXkybbM2zaorsy6QCryiKK7AUcAbCgZ6qqp5/qY0OmAU0A4zAt6qq/mzecJPmYKdLVOTrdJiYZDtHOx1zh6dt5kCj0ZjgwJDwYKAnJibx7f/uN8TdH/PS/YZEt/87kBhe2XfsbUP8gebF/Y6Otjx48DRR+/+ex5BknC//vNw24cEuYYzR0dEJniOp/RqSiCHxgTJhLsnRRz/l8b2nPL736rz1xwNNe60in9wj8tI9bl86HLtRo8UpX7H/nsNgZH/YLSnwIlsytQe/AJirqupviqJ0BxYCjV9q0w0oC5Qj9kBwXFGUIFVVr5gr2NepW6lQspNr6bQa6lYulObn0mg02NjYZJrzp7PqR9mkDpRDZwUTGfUco9GA0WBAr4/icfgNNBoNMc8j0cf9aI3PafpOIZ49e0ZUVCTPnkUSFRVJZGQkUVFRREXF/j57JRyD4TkxUU+JjnyEPvoZTs4lXxm+evkToBDZRbJVSlGUAkB1wCtu0x/AHEVRXFRVvZugaSdgkaqqBuCuoijrAB/g/8wc8ytMmVxLp9PgXdPyMyGKWEkdKBvUKPvKgTpnnsKJHqfTamhWtyQf1H872ed4+buZ13Gwy9hrF4TIKKZcL14c+EdVVT1A3O8bcdsTKgFcTXD7WhJt0kWBvDkY2NYNO1stOm3i3plOq8HOVsvAtm6Z+os0EXug1une/OWwTqehjUdZk/ZXt1KhV94Pr+zPTJ/shMiMMsc4Q5y4b4NTpYlLLiqWdWF98AV2HP2bZ1ExONrb0KhGMdp4lKVw/uy7qIOLSy5Lh2AWLi65GP1hLb5depgYveGVC9ZsdFq++LCmya9ll2YV2Bd2C73h9b14G52Wzk0r4JLJ3x/Z5TVOCWvLOT3yNaXAXweKKoqiU1VVH/dlapG47QldA0oCcd9mvdKjT1ZapyqwAfq3r/Lqx3ejIUuOU5siq47Bv07J/Dn4unfNZGfBNCVnG2BA28pvvMJ5QNvK2GTy90d2e41NYW05m+E0ySQlW+BVVb2jKMoJoAvwW9zv4y+NvwP4AR8rirKG2C9Z2wIeKY5YWL0CeXPQ3Vsxy5kt7mWcmdi7VpqnTRYiKzJ1iKY/sFRRlHFABNATQFGUzcA4VVWPAMuB2sCL0ycnqqp6yczxCpFi5jxgCJGVmFTgVVU9S2zxfnl7iwT/1gMDzBeaEEKItMh6i2kKIYQwiRR4IYTIpqTACyFENiUFXgghsikp8EIIkU1llitZdRB70r45mGs/WYW15QvWl7O15QvWl3Nq8k3wmCQnVMosC368B+y2dBBCCJFF1Qf2vLwxsxR4e6AmcBOQuVuFEMI0OqAwsVPERL18Z2Yp8EIIIcxMvmQVQohsSgq8EEJkU1LghRAim5ICL4QQ2ZQUeCGEyKakwAshRDYlBV4IIbKpzDJVQYooiuIKLCV2acBwoKeqqudfaqMDZgHNACPwraqqP2d0rOZgYr5jgc5ATNzPGFVV/TM6VnMxJecEbRXgODBPVdURGRel+Ziar6IoHYGxgIbY97Wnqqq3MzJWczHxfV0A+AUoDtgB24EhqqrGZHC4aaYoynTgA6AU4KaqalgSbcxat7JqD34BMFdVVVdgLrAwiTbdgLJAOaAuMEFRlFIZFqF5mZLvIaCmqqpVgN7ASkVRHDMwRnMzJecXfxALgXUZGFt6SDZfRVHeASYAXqqqViZ2io8HGRmkmZnyGo8Bzqiq6g64ATWA9hkXolmtI3ad6qtvaGPWupXlCnzcEb068Efcpj+A6oqiuLzUtBOwSFVVQ9wC4esAn4yL1DxMzVdVVX9VVZ/G3QwhtofnnGGBmlEKXmOAL4CNwLkMCs/sUpDvMGC6qqq3AFRVfaCqamTGRWo+KcjZCORSFEVL7JQmdsA/GRaoGamqukdV1evJNDNr3cpyBZ7Yj2r/xK0B+2It2Btx2xMqQeIj5bUk2mQFpuabUE/goqqqf2dAfOnBpJwVRXEHmgIzMzxC8zL1Na4IvK0oSrCiKMcURflKUZSsOuWiqTlPAlyJnafqFuCvqurejAw0g5m1bmXFAi/eQFGUBsT+UXSxdCzpSVEUW2AR0P9FkbACNoA74AU0AJoDPSwaUfrzIfYTaWGgKOChKEoHy4aUdWTFAn8dKBo39vpiDLZI3PaErgElE9wukUSbrMDUfFEUpS7wG9BWVVU13RrzEgAAAXFJREFUQ6M0L1NyLgyUATYrinIFGAp8rCjKTxkbqlmY+hpfBVapqhqlquojYD1QK0MjNR9Tc/4UWBE3ZPGA2JwbZWikGcusdSvLFXhVVe8AJ/ivh9oFOB43XpWQH7F/8Nq4cb22wOqMi9Q8TM1XUZSawEqgg6qqxzI2SvMyJWdVVa+pqppfVdVSqqqWAn4gduzykwwPOI1S8J7+HfBWFEUT9wmmCXAy4yI1nxTkfJnYM0pQFMUO8AReOfskGzFr3cpyBT5Of+BTRVHOEXuE7w+gKMrmuDMNAJYDl4DzwAFgoqqqlywRrBmYku88wBFYqCjKibgfN8uEaxam5JydmJKvL3AHOE1scTwFLLZArOZiSs5DgfqKooQSm/M5YofmshxFUWYpivI3UAwIUhTlVNz2dKtbMh+8EEJkU1m1By+EECIZUuCFECKbkgIvhBDZlBR4IYTIpqTACyFENiUFXgghsikp8EIIkU1JgRdCiGzq/wFI/ImY8hlFpQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.scatter(X[:, 0], X[:, 1], s=100)\n",
    "\n",
    "# 为每个点和它最近的两个点之间连上线\n",
    "K = 2\n",
    "\n",
    "for i in range(X.shape[0]):\n",
    "    for j in nearest_partition[i, :K+1]:\n",
    "        # 从X[i]连线到X[j]\n",
    "        # 使用一些zip的魔术方法画线\n",
    "        plt.plot(*zip(X[j], X[i]), color='black')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Each point in the plot has lines drawn to its two nearest neighbors.\n",
    "At first glance, it might seem strange that some of the points have more than two lines coming out of them: this is due to the fact that if point A is one of the two nearest neighbors of point B, this does not necessarily imply that point B is one of the two nearest neighbors of point A.\n",
    "\n",
    "图上的每个点都和与它最近的两个点相连。初看起来，你可能注意到有些点的连线可能超过2条，这很奇怪：实际原因是如果A是B的最近两个近邻之一，并不代表着B也必须是A的最近两个近邻之一。\n",
    "\n",
    "> Although the broadcasting and row-wise sorting of this approach might seem less straightforward than writing a loop, it turns out to be a very efficient way of operating on this data in Python.\n",
    "You might be tempted to do the same type of operation by manually looping through the data and sorting each set of neighbors individually, but this would almost certainly lead to a slower algorithm than the vectorized version we used. The beauty of this approach is that it's written in a way that's agnostic to the size of the input data: we could just as easily compute the neighbors among 100 or 1,000,000 points in any number of dimensions, and the code would look the same.\n",
    "\n",
    "虽然使用广播和逐行排序的方式完成任务可能没有使用循环来的直观，但是在Python中这是一种非常有效的方式。你可能忍不住使用循环的方式对每个点去计算它相应的最近邻，但是这种方式几乎肯定会比我们前面使用的向量化方案要慢很多。向量化的解法还有一个优点，那就是它不关心数据的尺寸：我们可以使用同样的代码和方法计算100个点或1,000,000个点以及任意维度数的数据的最近邻。\n",
    "\n",
    "> Finally, I'll note that when doing very large nearest neighbor searches, there are tree-based and/or approximate algorithms that can scale as $\\mathcal{O}[N\\log N]$ or better rather than the $\\mathcal{O}[N^2]$ of the brute-force algorithm. One example of this is the KD-Tree, [implemented in Scikit-learn](http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KDTree.html).\n",
    "\n",
    "最后，需要说明的是，当对一个非常大的数据集进行最近邻搜索时，还有一种基于树或相似的算法能够将时间复杂度从$\\mathcal{O}[N^2]$优化到$\\mathcal{O}[N\\log N]$或更好。其中一个例子是[KD-Tree](http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KDTree.html)。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Aside: Big-O Notation\n",
    "\n",
    "## 额外内容：大 O 复杂度\n",
    "\n",
    "> Big-O notation is a means of describing how the number of operations required for an algorithm scales as the input grows in size.\n",
    "To use it correctly is to dive deeply into the realm of computer science theory, and to carefully distinguish it from the related small-o notation, big-$\\theta$ notation, big-$\\Omega$ notation, and probably many mutant thereof.\n",
    "While these distinctions add precision to statements about algorithmic scaling, outside computer science theory exams and the remarks of pedantic blog commenters, you'll rarely see such distinctions made in practice.\n",
    "Far more common in the data science world is a less rigid use of big-O notation: as a general (if imprecise) description of the scaling of an algorithm.\n",
    "With apologies to theorists and pedants, this is the interpretation we'll use throughout this book.\n",
    "\n",
    "大O复杂度是一种衡量随着输入数据的增加，需要执行的操作的数量的量级情况的指标。要正确使用它，需要深入了解计算机科学的理论知识，要和其他相关的概念如小O复杂度，大$\\theta$复杂度，大$\\Omega$复杂度区分开来，更加不容易。虽然精确地描述出这些复杂度是属于算法的范畴，除了学院派计算机科学理论的测验和评分以外，你在其他应用领域很难看到这些严格的定义和划分。在数据科学领域中，我们不会使用这样死板的大O复杂度概念，虽然这和算法领域的概念在精确程度上有一定差距。带着对理论学者和学院派的歉意，本书将一直使用对大O复杂度的这种非精确概念解释。\n",
    "\n",
    "> Big-O notation, in this loose sense, tells you how much time your algorithm will take as you increase the amount of data.\n",
    "If you have an $\\mathcal{O}[N]$ (read \"order $N$\") algorithm that takes 1 second to operate on a list of length *N*=1,000, then you should expect it to take roughly 5 seconds for a list of length *N*=5,000.\n",
    "If you have an $\\mathcal{O}[N^2]$ (read \"order *N* squared\") algorithm that takes 1 second for *N*=1000, then you should expect it to take about 25 seconds for *N*=5000.\n",
    "\n",
    "大O复杂度，简单来说，会告诉你当你的数据增大时，你的算法运行需要的时间。例如你有一个$\\mathcal{O}[N]$（英文读作\"Order $N$\"）的算法，对于*N*=1000的数据量，它需要运行1秒，那么对于*N*=5000的数据量，算法需要执行的时间就为5秒。如果你的算法复杂度为$\\mathcal{O}[N^2]$（英文读作\"Order *N* squared\"），对于*N*=1000的数据量需要运行1秒，那么你可以预期当数据量增长为*N*=5000时，运行时间为25秒。\n",
    "\n",
    "> For our purposes, the *N* will usually indicate some aspect of the size of the dataset (the number of points, the number of dimensions, etc.). When trying to analyze billions or trillions of samples, the difference between $\\mathcal{O}[N]$ and $\\mathcal{O}[N^2]$ can be far from trivial!\n",
    "\n",
    "对于我们的目标来说，*N*通常代表着数据集的大小（数据点的数量，维度数等）。当我们需要分析的数据样本量达到百万级或十亿级时，$\\mathcal{O}[N]$和$\\mathcal{O}[N^2]$之间的差距将会是巨大的。\n",
    "\n",
    "> Notice that the big-O notation by itself tells you nothing about the actual wall-clock time of a computation, but only about its scaling as you change *N*.\n",
    "Generally, for example, an $\\mathcal{O}[N]$ algorithm is considered to have better scaling than an $\\mathcal{O}[N^2]$ algorithm, and for good reason. But for small datasets in particular, the algorithm with better scaling might not be faster.\n",
    "For example, in a given problem an $\\mathcal{O}[N^2]$ algorithm might take 0.01 seconds, while a \"better\" $\\mathcal{O}[N]$ algorithm might take 1 second.\n",
    "Scale up *N* by a factor of 1,000, though, and the $\\mathcal{O}[N]$ algorithm will win out.\n",
    "\n",
    "请记住大O复杂度本身并不能告诉你实际上运算消耗的时间，它仅仅能够告诉你当*N*变化时，运行时间会怎样随之发生变化。通常来说，$\\mathcal{O}[N]$复杂度的算法被认为肯定要比$\\mathcal{O}[N^2]$复杂度的算法要好。但对于小的数据集来说，好的大O复杂度算法并不一定能带来更快的执行效率。例如，某个特定情况下，$\\mathcal{O}[N^2]$复杂度的算法可能需要0.01秒的运行时间而$\\mathcal{O}[N]$复杂度的算法可能需要1秒。但是如果将*N*增大1000倍，那么$\\mathcal{O}[N]$复杂度的算法将会胜出。\n",
    "\n",
    "> Even this loose version of Big-O notation can be very useful when comparing the performance of algorithms, and we'll use this notation throughout the book when talking about how algorithms scale.\n",
    "\n",
    "我们这里使用的这种非严格定义的大O复杂度对于算法的性能也是有指示意义的，在本书的后续部分当我们讨论到算法范畴时都会应用到它。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!--NAVIGATION-->\n",
    "< [高级索引](02.07-Fancy-Indexing.ipynb) | [目录](Index.ipynb) | [格式化数据：NumPy里的结构化数组](02.09-Structured-Data-NumPy.ipynb) >\n",
    "\n",
    "<a href=\"https://colab.research.google.com/github/wangyingsm/Python-Data-Science-Handbook/blob/master/notebooks/02.08-Sorting.ipynb\"><img align=\"left\" src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open in Colab\" title=\"Open and Execute in Google Colaboratory\"></a>\n"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
